Національний університет “Львівська політехніка”
Кафедра ЕОМ
Курсова робота ( частина ІІ )
На тему:
“ Динамічні структури даних ”
з дисципліни:
"Програмування"
Вибір варіантів індивідуального завдання:
Вибір АТД: № = [(16) + (1993) + (97) ] % 4 + 1 = 3 ( АТД Список)
Номер завдання: № = [(10) + (1993) + (71) ] % 10 + 1=5
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
Завдання 1
Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи перший елемент списку містить значення 0. Якщо це так, то додати ще один елемент зі наченням 0 в кінець списку, якщо ні – то зі списку вилучити всі елементи зі наченням 0 .
Завдання 2
Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання такої операції над ними:
Обчислення полінома по заданим значенням X , Y , Z .
ЗМІСТ
1. ТЕОРЕТИЧНА ЧАСТИНА
2. ЗАВДАННЯ 3. ПОБУДОВА АТД
2.1. Постановка задачі
2.2. Динаміка вмісту
2.3. Результати виконання програми
3. ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД
3.1. Постановка задачі
3.2. Алгоритм розв’язання задачі
3.2.1. Словесний опис алгоритму
3.2.2. Граф-схема алгоритму
3.3. Результати виконання програми
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4
1.ТЕОРЕТИЧНА ЧАСТИНА
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
В бібліотеці стандартних шаблонів STL існує клас list, що підтримує двунаправлений лінійний список. В класі list визначений конструктор list, що створює порожній список. Нижче в таблиці наведені основні функції-члени класу list:
Функція-член
Опис
begin ()
Повертає двонаправлений ітератор для першого елемента
end ()
Повертає двонаправлений ітератор для позиції за останнім елементом
insert (pos , elem)
Вставляє копію elem в позицію ітератора pos і повертає позицію нового елемента
push_back (elem)
Додає копію elem в кінець списку
push_front (elem)
Вставляє копію elem в початок списку
pop_back (elem)
Вилучає останній елемент списку (не повертаючи його)
pop_front (elem)
Вилучає перший елемент списку (не повертаючи його)
remove (val)
Вилучає всі елементи списку зі значенням val
erase (pos)
Вилучає елемент в позиції ітератора pos і повертає позицію наступного елемента списку
clear ()
Вилучає всі елементи списку (контейнер залишається порожнім)
2. ЗАВД...
